package 链表题.删除倒数第N个节点;

import 链表题.ListNode;

/**
 * 方法一: 递归
 */
public class Test1 {

    /**
     * 方法一: 递归
     *
     * @param p 链表头
     * @param n 倒数第n位要删除的
     * @return 倒数第n-1位
     */
    public static int recursion(ListNode p, int n) {
        if (p == null) {
            return 0;
        }
        int nth = recursion(p.next, n);
        if (nth == n) {
            p.next = p.next.next;
        }
        return nth + 1;

    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode s = new ListNode(-1, head);
        recursion(s, n);
        return s.next;
    }

    public static void main(String[] args) {
        ListNode o5 = new ListNode(5, null);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);
        ListNode o = new ListNode(3, o1);
        System.out.println(o);
//        removeNthFromEnd(o, 5);
//        System.out.println(o);  这样写只要不删除o都不会有问题, 但是一旦删除o节点, 你打印的o节点任然还在
        System.out.println(removeNthFromEnd(o, 6));

    }
}
